// 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
// 假定 BST 有如下定义：
// 结点左子树中所含结点的值小于等于当前结点的值
// 结点右子树中所含结点的值大于等于当前结点的值
// 左子树和右子树都是二叉搜索树

// 思路，递归，中序遍历，有序
function findMode(root) {
    let result = []
    let count = 0
    let maxCount = 0
    let pre
    function dfs(root) {
        if (!root) {
            return
        }
        dfs(root.left)
        if (!pre) {
            count = 1
        } else if (pre.val === root.val) {
            count++
        } else {
            count = 1
        }
        pre = root
        if (count === maxCount) {
            result.push(root.val)
        }
        if (count > maxCount) {
            maxCount = count
            result = [root.val]
        }
        dfs(root.right)
    }
    dfs(root)
    return result
}

// 思路2， 迭代
function findMode2(root) {
    let stack = []
    let cur = root
    let pre
    let count = 0
    let maxCount = 0
    let result = []
    while (stack.length || cur) {
        if (cur) {
            stack.push(cur)
            cur = cur.left
        } else {
            let node = stack.pop()
            if (!pre) {
                count = 1
            } else if (pre.val === node.val) {
                count++
            } else {
                count = 1
            }
            pre = node
            if (count === maxCount) {
                result.push(node.val)
            }
            if (count > maxCount) {
                maxCount = count
                result = [node.val]
            }
            cur = node.right
        }
    }
    return result
}
let root = {
    val: 1,
    right: {
        val: 2,
        left: {
            val: 2
        }
    }
}

console.log(findMode(root))
console.log(findMode2(root))